/**
 * 项目名称: Topic_632.cpp
 * 项目路径: study/DataStructure/刷题/一轮/第十三天 数组+双指针
 * 编辑时间: 2024年09月15日19时55分49秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

/**
 * 做题思路:
 *  1. 从一个区间中选出最小值
 *  2. 从别的区间中选出比这个值大且最接近这个值的数
 *  3. 不断缩小区间,当某一个数组用完时,即结束
 * 考察知识点:
 *  1. 最小堆求最小值
 *  2. 堆中放入三元组
 *  3. 边界处理,当一个数组用完时,表明这个数组已经没有比别的数组大的数了,即结束
 */
class Solution {
public:
    vector<int> smallestRange(vector<vector<int>> &nums) {
        typedef vector<int> VI;
        VI res; //存储结果,代表最小范围[l,r]
        //最小值,每个堆元素都是三元组,分别为,值,数组下标,对应数组内下标
        priority_queue<VI, vector<VI>, greater<VI>> heap;
        int maxv = INT16_MIN;//记录当前堆中的最大值

        //初始化最小堆,将每个数组的第一个元素加入到堆中,同时更新最大值
        for (int i = 0; i < nums.size(); i++) {
            heap.push({nums[i][0], i, 0});
            maxv = max(maxv, nums[i][0]);//更新当前的最大值
        }

        //从最小堆中弹出元素,维护最小范围
        while (heap.size()) {
            auto t = heap.top();//获取最小元素
            heap.pop();

            int l = t[0];//当前最小值
            int r = maxv;// 当前最大值

            // 如果当前范围更小,更新结果
            if (res.empty() || res[1] - res[0] > r - l)res = {l, r};

            int i = t[1];// 该最小值对应的数组索引
            int j = t[2] + 1;// 该数组内下一个元素的索引

            // 如果当前数组还有下一个元素
            if (j < nums[i].size()) {
                heap.push({nums[i][j], i, j});//将下一个元素加入堆中
                maxv = max(maxv, nums[i][j]);// 更新最大值
            } else break;//数组用完,退出循环
        }
        return res;
    }
};
